package 哈夫曼树;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class 哈夫曼树 {
	public static void main(String[] args) {
		//创建数组，用于构建哈夫曼树
//		int[] arr = {13,7,8,3,29,6,1};
		int[] arr = {7,19,2,6,32,3,21,10};
		
		//创建哈夫曼树
		HuffmanTree tree = new HuffmanTree();
		Node root = tree.huffmanTree(arr);
		System.out.println(root);
		tree.preOrder(root);
	}
}
/**
 * 哈夫曼树
 * @author PC
 *
 */
class HuffmanTree {
	
	
	/**
	 * 构建哈夫曼树
	 * @param arr
	 * @return
	 */
	public Node huffmanTree(int[] arr) {
		//首先将数组转成一个个单独的树，放到List中
		List<Node> nodes = new ArrayList<>();
		for(int i : arr) {
			nodes.add(new Node(i));
		}
		
		//构建哈夫曼树
		//循环构建，直到剩下最后一个树
		while(nodes.size() > 1) {
			//排序，从小到大，才能取出需要的两个最小值
			Collections.sort(nodes);
			
			//找出最小，次小值，分别作为左右子结点
			Node leftNode = nodes.get(0);
			Node rightNode = nodes.get(1);
			
			//生成新的结点作为父节点
			Node parentNode = new Node(leftNode.value + rightNode.value);
			parentNode.left = leftNode;
			parentNode.right = rightNode;
			
			//取出已经使用的两个树，放入新生成的树
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			nodes.add(parentNode);
			
		}
		//返回根，就是剩下的最后一个，且是最大
		return nodes.get(0);
	}
	
	/**
	 * 前序遍历
	 * @param node 根
	 */
	public void preOrder(Node node) {
		if(node == null) {
			return;
		}else {
			System.out.println(node.value);
			preOrder(node.left);
			preOrder(node.right);
		}
	}
}

/**
 * 结点，要使用Collections的排序，就要实现Comparable类
 * @author PC
 *
 */
class Node implements Comparable<Node>{
	public int value;
	public Node left;
	public Node right;
	
	public Node() {
		super();
	}
	public Node(int value) {
		super();
		this.value = value;
	}
	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}
	
	/**
	 * 重写排序规则
	 */
	@Override
	public int compareTo(Node o) {
		// 此为从小到大，加负号-(this.value-o.value)表示从大到小
		//Collections.sort()方法使用
		return this.value-o.value;
	}
	
	
}